package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/'>根据前序和后序遍历构造二叉树(Construct Binary Tree from Preorder and Postorder Traversal)</a>
 * <p>给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。</p>
 * <p>如果存在多个答案，您可以返回其中 任何 一个。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
 *      输出：[1,2,3,4,5,6,7]
 *
 * 示例 2:
 *      输入: preorder = [1], postorder = [1]
 *      输出: [1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= preorder.length <= 30</li>
 *         <li>1 <= preorder[i] <= preorder.length</li>
 *         <li>preorder 中所有值都 不同</li>
 *         <li>postorder.length == preorder.length</li>
 *         <li>1 <= postorder[i] <= postorder.length</li>
 *         <li>postorder 中所有值都 不同</li>
 *         <li>保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0105ConstructBinaryTreeFromPreorderAndInorderTraversal_M
 * @see LC0106ConstructBinaryTreeFromInorderAndPostorderTraversal_M
 * @see LC0889ConstructBinaryTreeFromPreorderAndPostorderTraversal_M
 * @since 2024/3/1 15:06
 */
public class LC0889ConstructBinaryTreeFromPreorderAndPostorderTraversal_M {

    static class Solution {
        public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
            Map<Integer, Integer> postorderValue2IndexMap = new HashMap<>();
            for (int i = 0; i < postorder.length; i++) {
                postorderValue2IndexMap.put(postorder[i], i);
            }
            return doBuildTree(preorder, postorder, postorderValue2IndexMap, 0, preorder.length - 1, 0, postorder.length - 1);
        }

        /**
         * <p>令 n 为二叉树的节点数目，那么根据前序遍历与后序遍历的定义，preorder[0] 与postorder[n−1] 都对应二叉树的根节点。
         * <p>
         * 获取根节点后，我们需要划分根节点的左子树与右子树，考虑两种情况：
         *     <ol>
         *         <li>原二叉树的根节点的左子树不为空，那么 preorder[1] 对应左子树的根节点；</li>
         *         <li>原二叉树的根节点的左子树  为空，那么 preorder[1] 对应右子树的根节点。</li>
         *     </ol>
         *     对于以上两种情况，我们无法区分 preorder[1] 到底是哪种情况。<br>
         *     但是对于第二种情况，将原二叉树的右子树移到左子树后得到的二叉树的前序遍历数组与后序遍历数组与原二叉树相同，所以我们只需要考虑第一种情况。
         * </p>
         * <p>因为二叉树的值互不相同，我们可以在 postorder 中找到 postorder[k]=preorder[1]，那么左子树的节点数目为 k+1。</p>
         * <p>基于此，我们可以对 preorder 和 postorder 进行分治处理，即将 preorder 划分为根节点、左子树节点和右子树节点三个部分，postorder 也划分为左子树节点、右子树节点和根节点三个部分。</p>
         * <p>
         *     那么问题划分为：
         *     <ul>
         *         <li>根据左子树节点的前序遍历与后序遍历数组构造二叉树；</li>
         *         <li>根据右子树节点的前序遍历与后序遍历数组构造二叉树。</li>
         *     </ul>
         * </p>
         * <p>同时当节点数目为 1 时，对应构造的二叉树只有一个节点。我们可以递归地对问题进行求解，就可得到构造的二叉树。</p>
         */
        private TreeNode doBuildTree(int[] preorder, int[] postorder, Map<Integer, Integer> postorderValue2IndexMap,
                                     int preorderLeftBorder, int preorderRightBorder, int postorderLeftBorder, int postorderRightBorder) {
            if (preorderLeftBorder > preorderRightBorder) {
                return null;
            }
            // leftCount：左子树节点的数量
            int leftCount = 0;
            if (preorderLeftBorder < preorderRightBorder) {
                leftCount = postorderValue2IndexMap.get(preorder[preorderLeftBorder + 1]) - postorderLeftBorder + 1;
            }
            TreeNode root = new TreeNode(preorder[preorderLeftBorder]);
            root.left = doBuildTree(preorder, postorder, postorderValue2IndexMap,
                    preorderLeftBorder + 1, preorderLeftBorder + leftCount,
                    postorderLeftBorder, postorderLeftBorder + leftCount - 1);
            root.right = doBuildTree(preorder, postorder, postorderValue2IndexMap,
                    preorderLeftBorder + leftCount + 1, preorderRightBorder,
                    postorderLeftBorder + leftCount, postorderRightBorder - 1
            );
            return root;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode.printTree(solution.constructFromPrePost(new int[]{1, 2, 4, 5, 3, 6, 7}, new int[]{4, 5, 2, 6, 7, 3, 1}));
    }
}
